package graphic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * @author ZhangyiA
 * @describe: 用来存储扩展过程中的子图
 * @date 2021/06/25
 */

public class SubGraph {
    private Graph graph = null;
    private int id;
    private int degree; // 按照度进行聚类
    public Map<Integer , Integer> vertexDeg ; // 节点 和 节点的度 , 还可以用来判断一个节点是否已被添加
    public Map<Integer , Integer> vertexLabelCount; // 每一个节点标签出现的次数
    public ArrayList<Integer> vertex; // 记录顶点id
    public Map<Integer , Integer> edgeLabelCount; // 每个边标签出现的次数
    public Set<Integer> edges; // 只记录边的标号
    public float NIS[][];
    private PriorityQueue<Edge> priorityQueue;

    public SubGraph(){
        this.degree = 0;
        this.vertexDeg = new HashMap<>();
        this.edgeLabelCount = new HashMap<>();
        this.vertexLabelCount = new HashMap<>();
        this.vertex = new ArrayList<>();
        this.edges = new HashSet<>();
    }

    public SubGraph(Graph graph , int id){
        this();
        this.graph = graph;
        // 该优先队列是保证下一次添加的 边 是 能到达顶点具有最大顶点影响的
        this.priorityQueue = new PriorityQueue<>((e1,e2)->{
            if(graph.vertices[e2.getVertexTo()].verInfluence == graph.vertices[e1.getVertexTo()].verInfluence){
                return e1.getVertexFrom() - e2.getVertexFrom();
            } else {
                return graph.vertices[e2.getVertexTo()].verInfluence > graph.vertices[e1.getVertexTo()].verInfluence ? 1 : -1;
            }
        });
        this.id = id;
    }

    // 添加第一个点 , 作为初始化
    public void init(int nodeId){
        vertexLabelCount.put(graph.vertices[nodeId].getLabel(), 1);
        vertex.add(nodeId);
        vertexDeg.put(nodeId , 0);
        for(int i = graph.head[nodeId] ; i != -1 ; i = graph.edges[i].getNext()){
            priorityQueue.offer(graph.edges[i]);
        }
    }

    public boolean extend(){
        while(!priorityQueue.isEmpty()) {
            Edge edge = priorityQueue.poll();
            if (addEdge(edge)) {
                int to = edge.getVertexTo();
                for (int i = graph.head[to] ; i != -1 ; i = graph.edges[i].getNext()){
                    priorityQueue.offer(graph.edges[i]);
                }
                return true;
            }
        }
        return false;
    }

    // 判断边是否添加成功 , 防止重复边再次添加
    public boolean addEdge(Edge edge){
        int reverse = edge.getId();
        reverse -= (reverse & 1) == 1 ? 1 : -1;  // 因为正反两条边 是挨着的， id 互为奇偶 ， 判断一条边是否已经被添加，需要同时判断正反两天边
        if(edges.contains(edge.getId()) || edges.contains(reverse)) return false;  // 同时判断当前边是够已被添加, 和 反向边
        edges.add(edge.getId());

        this.degree += 2; // 任何情况 , 添加一条边 , 又或者一条边一个顶点  , degree + 2 恒成立  ,  前提是 在 init 的是 degree 初始化为 0
        int vertexFrom = edge.getVertexFrom();
        int fromLabel = graph.vertices[vertexFrom].getLabel();
        int vertexTo = edge.getVertexTo();
        int toLabel = graph.vertices[vertexTo].getLabel();
        int label = edge.getLabel();

        // 修改顶点的 度 , 顶点标签出现的次数 , 新顶点添加
        addVertex(vertexFrom , fromLabel);
        addVertex(vertexTo , toLabel);

        // 边标号出现的次数
        addEdgeLabelCount(label);
        return true;
    }

    public String getNIS(){
        computeNIS();
        Arrays.sort(NIS , (n1 , n2) -> n2[1] > n1[1] ? 1 : -1);
        StringBuffer nis = new StringBuffer();
        for(int i = 0 ; i < NIS.length ; i ++){
            nis.append(graph.vertices[(int)NIS[i][0]].getLabel());
        }
        char[] ch = nis.toString().toCharArray();
        Arrays.sort(ch);
        return new String(ch);
    }

    // 如果两个子图的 NIS 相等时 , 进一步通过图的 bfs 判断图是否为同构
    public int getMaxImportance(){
        return (int) this.NIS[0][1];
    }

    private void computeNIS(){
        this.NIS = new float[vertex.size()][2];
        for(int i = 0 ; i < vertex.size() ; i ++){
            int val = vertex.get(i);
            NIS[i][0] = val;
            int deg = vertexDeg.get(val);
            int cnt = vertexLabelCount.get(graph.vertices[val].getLabel());
            NIS[i][1] = (float) (deg * 1.0) / cnt;
        }
    }

    private void addVertex(int id , int label){
        if(vertexDeg.containsKey(id)){
            vertexDeg.put(id , vertexDeg.get(id) + 1);
        } else {
            vertex.add(id); // 说明该顶点是第一被添加到图中
            vertexDeg.put(id , 1);
            int count = vertexLabelCount.containsKey(label) ? vertexLabelCount.get(label) : 0;
            vertexLabelCount.put(label , count + 1);
        }
    }

    private void addEdgeLabelCount(int edge_label){
        if(edgeLabelCount.containsKey(edge_label)){
            edgeLabelCount.put(edge_label , edgeLabelCount.get(edge_label) + 1);
        } else {
            edgeLabelCount.put(edge_label , 1);
        }
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public int getDegree() {
        return degree;
    }

    public void setDegree(int degree) {
        this.degree = degree;
    }

    @Override
    public String toString() {
        return "SubGraph{" +
                "graph=" + graph +
                ", id=" + id +
                ", degree=" + degree +
                ", NIS=" + getNIS() +
                ", vertexDeg=" + vertexDeg +
                ", vertexLabelCount=" + vertexLabelCount +
                ", vertex=" + vertex +
                ", edgeLabelCount=" + edgeLabelCount +
                ", edges=" + edges +
                '}';
    }
}
